package 回溯;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 计算各个位数不同的数字的个数.java
 * @Description TODO
 * @createTime 2020年11月02日 21:43:00
 * 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
 *
 * 示例:
 *
 * 输入: 2
 * 输出: 91
 * 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
 *
 * 还是基本的回溯算法 注意减枝
 */
public class 计算各个位数不同的数字的个数 {
//    class Solution {
//        int count=0;
//        public int countNumbersWithUniqueDigits(int n) {
//            boolean[] used=new boolean[10];
//            backtrack(n,used,0);
//
//            return count+1;
//        }
//
//        void backtrack(int n,boolean[] used,int depth){
//            if(depth==n){
//                return ;
//            }
//            for(int i=0;i<=9;i++){
//                if(used[i]||(depth==0&&i==0)){
//                    continue;
//                }
//                used[i]=true;
//                count++;
//                backtrack(n,used,depth+1);
//                used[i]=false;
//
//            }
//        }
//    }
//    class Solution {
//        public int countNumbersWithUniqueDigits(int n) {
//            dfs(n);
//
//            return count + 1;
//        }
//
//        int count = 0;
//        List<Integer> a = new ArrayList<>();
//
//        public void dfs (int n){
//            if (a.size() == n) {
//                return;
//            }
//
//            for (int i = 0;i <= 9;i++) {
//                if (a.contains(i) || (a.isEmpty() && i == 0)) continue;
//                a.add(i);
//                count += 1;
//                dfs(n);
//                a.remove(a.size() - 1);
//            }
//
//        }
//    }
}
